#include "bitree.h"
using std::list;

BiTree::BiTree()
{
	if(this->InitBiTree() != OK)
		exit(ERROR);
}

Status BiTree::InitBiTree()
{
	this->root = NULL;
	return OK;
}

Status BiTree::DestroyBiTree()
{
	return this->ClearBiTree(this->root);
	this->root = NULL;
}

Status BiTree::CreateBiTree(void (*func)(BiTNode *T))
{
	(*func)(this->root);
	return OK;
}

Status BiTree::ClearBiTree(BiTNode *T = NULL)
{
	if(T == NULL)
		T = this->root;
	if(T)
	{
		if(T->lchild)
			this->ClearBiTree(T->lchild);
		if(T->rchild)
			this->ClearBiTree(T->rchild);
		free(T);
		return OK;
	}
	else
		return ERROR;
	return OK;
}

bool BiTree::BiTreeEmpty()
{
	return (this->root == NULL);
}

int BiTree::BiTreeDepth(BiTNode *T = NULL, bool isroot = true)
{
	int ldep, rdep;
	if(isroot)
		T = this->root;
	if(T == NULL)
		return 0;
	else
	{
		ldep = this->BiTreeDepth(T->lchild, false);
		rdep = this->BiTreeDepth(T->rchild, false);
		return (ldep>rdep?ldep:rdep)+1;
	}
}

BiTNode *BiTree::Root()
{
	return this->root;
}

TElemType BiTree::Value(BiTNode *e)
{
	return e->data;
}

Status BiTree::Assign(BiTNode *e, TElemType value)
{
	e->data = value;
	return OK;
}

BiTNode *BiTree::Parent(BiTNode *e)
{
	return e->parent;
}

BiTNode *BiTree::LeftChild(BiTNode *e)
{
	return e->lchild;
}

BiTNode *BiTree::RightChild(BiTNode *e)
{
	return e->rchild;
}

BiTNode *BiTree::LeftSibling(BiTNode *e)
{
	if(e->parent->lchild == e)
		return NULL;
	else
		return e->parent->lchild;
}

BiTNode *BiTree::RightSibling(BiTNode *e)
{
	if(e->parent->rchild == e)
		return NULL;
	else
		return e->parent->rchild;
}

Status BiTree::InsertChild(BiTNode *p, int LR, BiTNode *c)
{
	BiTNode *temp;
	if(this->root == NULL)
	{
		printf("insert in root: %d\n", c->data);
		root = c;
		return OK;
	}
	if(LR == 0)
	{
		if(c == NULL || c->rchild != NULL)
			return ERROR;
		temp = p->lchild;
		p->lchild = c;
		c->rchild = temp;
		c->parent = p;
		if(temp)
			temp->parent = c;
		printf("insert in left child of %d: %d\n", p->data, c->data);
	}
	else
	{
		if(c == NULL || c->rchild != NULL)
			return ERROR;
		temp = p->rchild;
		p->rchild = c;
		c->rchild = temp;
		c->parent = p;
		if(temp)
			temp->parent = c;
		printf("insert in right child of %d: %d\n", p->data, c->data);
	}
	return OK;
}

Status BiTree::DeleteChild(BiTNode *p, int LR)
{
	if(LR == 0)
	{
		if(p->lchild)
		{
			this->ClearBiTree(p->lchild);
			p->lchild = NULL;
		}
		return OK;
	}
	else
	{
		if(p->rchild)
		{
			this->ClearBiTree(p->rchild);
			p->rchild = NULL;
		}	
		return OK;
	}
	return ERROR;
}

Status BiTree::PreOrderTraverse(Status (*visit)(TElemType e), BiTNode *T = NULL, bool isroot = true)
{
	if(isroot)
		T = this->root;
	if(T == NULL)
		return OK;
	if((*visit)(T->data) == OK)
		if(this->PreOrderTraverse(visit, T->lchild, false) == OK)
			if(this->PreOrderTraverse(visit, T->rchild, false) == OK)
				return OK;
	return ERROR;
}

Status BiTree::InOrderTraverse(Status (*visit)(TElemType e), BiTNode *T = NULL, bool isroot = true)
{
	if(isroot)
		T = this->root;
	if(T == NULL)
		return OK;
	if(this->InOrderTraverse(visit, T->lchild, false) == OK)
		if((*visit)(T->data) == OK)
			if(this->InOrderTraverse(visit, T->rchild, false) == OK)
				return OK;
	return ERROR;
}

Status BiTree::PostOrderTraverse(Status (*visit)(TElemType e), BiTNode *T = NULL, bool isroot = true)
{
	if(isroot)
		T = this->root;
	if(T == NULL)
		return OK;
	if(this->PostOrderTraverse(visit, T->lchild, false) == OK)
		if(this->PostOrderTraverse(visit, T->rchild, false) == OK)
			if((*visit)(T->data) == OK)
				return OK;
	return ERROR;
}

Status BiTree::LevelOrderTraverse(Status (*visit)(TElemType e))
{
	list<BiTNode *> nodeList;
	BiTNode *temp;
	Status st;
	if(this->root)
		nodeList.push_back(this->root);
	else
		return ERROR;
	while(!nodeList.empty())
	{
		temp = nodeList.front();
		nodeList.pop_front();
		st = (*visit)(temp->data);
		if(st != OK)
			return ERROR;
		if(temp->lchild)
			nodeList.push_back(temp->lchild);
		if(temp->rchild)
			nodeList.push_back(temp->rchild);
	}
	return OK;
}
